package com.linchong.dynamicprogramming.medium;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-26 10:32
 * @Description: CoinsInALine$
 * 有一排N个石子，Alice,Bob两人轮流取石子，
 * 每次一个人可以从最右边取走一个或两个石子，
 * 取走最后石子的人胜，
 * 问先手Alice是否必胜（先手必胜：true,先手必败：false）
 * <p>
 * 例子：
 * 输入：N=5
 * 输出：true（先手取走2个石子，剩下3个石子，无论后手怎么拿，先手都可以取走最后一个石子）
 * <p>
 * step 1:确定状态
 * 博弈型动态规划通常从第一步开始分析，而不是最后一步，因为局面越来越简单，石子数越来越小
 * <p>
 * 面对N个石子，先手Alice第一步可以拿1个或2个石子，
 * 这样后手Bob就面对N-1个石子或者N-2个石子
 * <p>
 * 先手Alice一定会选择能让自己赢的一步，因此双方都是采用最优策略
 * <p>
 * 假设后手Bob面对N-1个石子，
 * 其实这和一开始Bob是先手，有N-1个石子的情况是一样的
 * 那么Bob也会选择让自己赢的一步：取走一个或两个石子
 * <p>
 * 之后Alice面对新的局面，自己成为新的先手，选择让自己赢的一步
 * <p>
 * 必胜 VS 必败
 * <p>
 * 怎么选择让自己赢得一步
 * 走了这一步，对手面对剩下的石子，他必败
 * <p>
 * 子问题：
 * 面对N个石子，是否先手必胜->需要直到面对N-1个石子和N-2个石子，是否先手必胜
 * 状态：设f[i]表示面对i个石子，是否先手必胜(f[i]=true/false)
 * <p>
 * step 2:转义方程：
 * 设f[i]表示面对i个石子，是否先手必胜（f[i]=TRUE/FALSE）
 * f[i]=   TRUE,f[i-1]==false and f[i-2]==false  拿1个或2个石子都必胜
 * TRUE,f[i-1]==false and f[i-2]==true   拿一个石子必胜
 * TRUE,f[i-1]==true and f[i-2]==false   拿两个石子必胜
 * FALSE,f[i-1]==true and f[i-2]==true   必败
 * <p>
 * 即：f[i]=f[i-1]==FALSE OR f[i-2] == FALSE
 * <p>
 * step 3:初始条件和边界情况
 * 设f[i]表示面对i个石子，是否先手必胜（f[i]=TRUE/FALSE）
 * f[i] = f[i-1]==FALSE OR f[i-2]==FALSE
 * f[0]=FALSE --面对0个石子，先手必败
 * f[1]=f[2]=TRUE --面对1个石子或两个石子，先手必胜
 * <p>
 * step 4:计算顺序
 * f[0],f[1],f[2],...,f[N]
 * <p>
 * 如果f[N]=TRUE,则先手必胜，否则，先手必败
 * <p>
 * 时间复杂度O(N),空间复杂度O(N),可以滚动数组优化至O(1)
 */
public class CoinsInALine {

	public boolean firstWillWin(int n) {
		if (n == 0) {
			return false;
		}
		if (n <= 2) {
			return true;
		}

		boolean[] f = new boolean[n + 1];
		f[0] = false;
		f[1] = f[2] = true;
		for (int i = 3; i <= n; i++) {
			f[i] = (!f[i - 1] || !f[i - 2]);
		}
		return f[n];
	}

	public static void main(String[] args) {
		int n = 5;
		CoinsInALine instance = new CoinsInALine();
		System.out.println(instance.firstWillWin(n));
	}

	//数学解法
	//0 1 2 3 4 5 6 7 8 9 10
	//F T T F T T F T T F T
	// return n%3 != 0;
}
